In many settings, it is useful to certify data, as well as to revoke data that was previously certified. For instance, in a Public Key Infrastructure (PKI), it may be useful to certify users' public keys. Such certification may be provided in the form of a certificate which contains the certified data and vouches authenticity of the certified data.
In a digital signature scheme, each user U chooses a signing key SK.sub.u and a matching verification key, PK.sub.u. User U uses SK.sub.u to compute a digital signature of a message m, SIG.sub.u (m), while anyone knowing that PK.sub.u is U's public key can verify that SIG.sub.u (m) is U's signature of m. Finding SIG.sub.u (m) without knowing SK.sub.u is practically impossible. On the other hand, knowledge of PK.sub.u does not give any practical advantage in computing SK.sub.u. For this reason, it is in U's interest to keep SK.sub.u secret (so that only he can digitally sign for U) and to make PK.sub.u as public as possible (so that everyone dealing with U can verify U's digital signatures). At the same time, in a world with millions of users, it is essential in the smooth flow of business and communications to be certain that PK.sub.u really is the legitimate key of user U. To this end, users' public keys are often "certified" by a certificate that serves as proof that U is the legitimate owner of PK.sub.u. At the same time it is also useful to be able to revoke some of the already-issued certificates when U is no longer the legitimate owner of PK.sub.u (for whatever reason) and/or when SK.sub.u has been compromised. Of course, the need for certification and certificate revocation extends beyond certifying public keys.
In many instances, certificates for users' public keys are produced and revoked by certifying authorities called CA's. A complete public key infrastructure may involved other authorities (e.g., PCAs) who may also provide similar services (e.g., they may certify the public keys of their CA's). The present discussion can be easily applied to such other authorities in a straight-forward manner.
A CA may be a trusted agent having an already certified (or universally known) public key. To certify that PK.sub.u is U's public key, a CA typically digitally signs PK.sub.u together with (e.g., concatenating it with) U's name, a certificate serial number, the current date (i.e., the certification or issue date), and an expiration date. The CA's signature of PK.sub.u is then inserted in a Directory and/or given to U himself. Note that, before certifying U's public key, it is necessary to perform additional steps, such as properly identifying user U. However, these additional steps are optional.
Upon receiving the (alleged) digital signature of user U of a message M, SIG.sub.u (M), a recipient R needs to obtain a certificate for PK.sub.u. (In fact, SIG.sub.u (M) may be a correct digital signature of M with respect to some public key PK.sub.u, but R has no guarantee that PK.sub.u is indeed U's public key. Recipient R may obtain this certificate from the Directory, or from his own memory (if he has previously cached it), or from U himself. Having done this, R verifies (1) the correctness of the CA's certificate for PK.sub.u with respect to the CA's public key, and (2) the correctness of SIG.sub.u (M) with respect to PK.sub.u. If the CA's public key is not universally known, or cached with R, then a certificate for the CA's key may also be obtained.
Certificate retrieval is thus possible, although not necessarily cheap.
Unfortunately, however, this is not the only retrieval that R needs to do. In addition, it is important that R makes sure that the certificate for PK.sub.u has not been revoked. This check, of course, may not be needed after the certificate's expiration date, but may be needed during the certificate's alleged lifetime. A user's certificate can be revoked for a variety of reasons, including key compromise and the fact that the user is no longer associated with a particular CA.
To enable a recipient to establish whether a given certificate has been revoked, it is known to have each CA periodically issues a Certificate Revocation List (CRL for short). A CRL may consist of the issuer's digital signature of a header comprising the issuer's name (as well as the type of his signature algorithm), the current date, the date of the last update, and the date of the next update, together with a complete list of revoked certificates (whose date has not yet expired), each with its serial number and revocation date. Since it is expected that a CA revokes many certificates, a CRL is expected to be quite long. It is envisaged that the CRL is provided to a directory who may then distribute the CRL to end users.
After performing some checks on the CA's CRL (e.g., checking the CA's digital signature, checking that the CRL has arrived at the expected time, that a certificate declared revoked in the previous CRL of that CA--and not yet expired still is revoked in the current CRL, etc.), the Directory stores it under its CA name.
When a user queries the Directory about the revocation of a certificate issued by a given CA, the Directory responds by sending to the user the latest CRL of that CA. The user can then check the CRL signature, the CRL dates (so as to receive a reasonable assurance that he is dealing with the latest one), and whether or not the certificate of interest to him belongs to it.
While CRLs are quite effective in helping users establishing which certificates are no longer deemed valid, they are also extremely expensive, because they tend to be very long and need to be transmitted very often.
The National Institute of Standard and Technology has tasked the MITRE Corporation to study the organization and cost of a Public Key Infrastructure (PKI) for the Federal Government. This study estimates that CRLs constitute by far the largest entry in the Federal PKI's cost list. According to MITRE's estimates/assumptions, in the Federal PKI there are about three million users, each CA serves 30,000 users, 10% of the certificates are revoked (5% because of key compromise and 5% because of change in affiliation with the organization connected to a given CA), CRLs are sent out bi-weekly, and the recipient of a digital signature requests certificate information 20% of the time (assuming that the remaining 80% of the time he will be dealing with public keys in his cache). The study envisages that each revoked certificate is specified in a CRL by means of about 9 bytes: 20 bits of serial number and 48 bits of revocation date. Thus, in the Federal PKI, each CRL is expected to comprise thousands of certificate serial numbers and their revocation dates; the header, however, has a fixed length, consisting of just 51 bytes.
At two cents per kilobyte, the impact of CRL transmission on the estimated yearly costs of running the Federal PKI is stunning: if each federal employee verifies one hundred digital signatures per day on average, then the total PKI yearly costs are $10,848 million of which 10,237 million is due to CRL transmission. If each employee is assumed to verify just five digital signatures a day on average, then the total PKI yearly costs are $732 million, of which 563 million is due to CRL transmission.
The MITRE study thus suggests that any effort should be made to find designs alternative to and cheaper than conventional CRL's.
In addition, we contend that it is possible for a user to query the Directory with a serial number not corresponding to any issued certificate. (Indeed, while many times the user has already seen a certificate and accesses the Directory just to confirm the current validity of that certificate, at other times the user wishes to obtain the corresponding certificate from the Directory). If the corresponding certificate does not exist, the Directory is at a loss as to how to proceed. If the Directory responds truthfully, it may not be believed by the user. If the Directory gives the users all the certificates in its possession (or those relative to a given CA) the user may suspect that the Directory left out the certificate of interest. Indeed, even if the Directory gives the user the latest CRL of a given CA, this does not prove to the user that the certificate in question does not exist. (In fact, the actions of the Directory may actually be interpreted as saying that the certificate is valid because it does not appear to have been revoked.) Thus in this thorny situation the Directory would have to be trusted.